package 剑指Offer.hard;

import jdk.nashorn.internal.ir.CallNode;

import java.util.Deque;
import java.util.LinkedList;

public class 序列化二叉树 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public class Codec {

        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
            if (root == null) return "[]";
            StringBuilder sb = new StringBuilder();
            sb.append("[");
            Deque<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()) {
                TreeNode poll = queue.poll();
                if (poll != null) {
                    sb.append(poll.val + ",");
                    queue.add(poll.left);
                    queue.add(poll.right);
                } else {
                    sb.append("null,");
                }
            }
            sb.deleteCharAt(sb.length() - 1).append("]");
            return sb.toString();
        }

        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
            if (data.equals("[]")) return null;
            //分割为结点数组
            String[] split = data.substring(1, data.length() - 1).split(",");
            Deque<TreeNode> queue = new LinkedList<>();
            //添加根结点
            TreeNode root = new TreeNode(Integer.parseInt(split[0]));
            queue.add(root);
            int i = 1;
            while (!queue.isEmpty()) {
                TreeNode poll = queue.poll();
                if (!split[i].equals("null")) {
                    poll.left = new TreeNode(Integer.parseInt(split[i]));
                    queue.add(poll.left);
                }
                i++;
                if (!split[i].equals("null")) {
                    poll.right = new TreeNode(Integer.parseInt(split[i]));
                    queue.add(poll.right);
                }
                i++;
            }
            return root;
        }
    }
}
